1

[CERC2017] Buffalo Barricades

考虑算出每个点最终被哪个矩形包含，这种情况下只有相互交叉的两个矩形可能存在覆盖关系。

此时交叉在 $y$$y$ 轴上只有一种体现，那就是比一条线靠后的射线，被这条射线在 $y$$y$ 轴上恰好覆盖。

因此按矩形的 $x$$x$ 坐标降序扫描线，用 set 维护射线的端点。因为矩形之间是编号小的覆盖在上面，所以考虑加入一条新的射线，如果被这条射线覆盖到的端点里面，有一个编号比它大，那么应当删除这个端点。

set 维护的实际上是这样一个结构：

1
----.
2
    |
3
--------.
4
        |
5
-----------.
6
           |

最终导致的结果，应当是端点在当前线之前的射线，编号都比当前线小。那么考虑一个点属于的矩形，就是覆盖这个点的那条射线。

考虑这样计算，只存在一种情况的矩形没办法准确计算答案，就是矩形 $A$$A$ 包含矩形 $B$$B$，且矩形 $A$$A$ 比矩形 $B$$B$ 早出现。

考虑最后加入的矩形，答案一定是正确计算的。而一个没有被正确计算答案的矩形一定较早出现。

按照加入顺序倒序遍历所有矩形，那么找到在最终图形上，包含掉这个矩形的矩形，这只有一个，把答案合并到这上面即可。

xxxxxxxxxx
44
1
#include<bits/stdc++.h>
2
const int CN = 6e5 + 10;
3
using namespace std;
4
int read(){
5
    int s = 0, ne = 1; char c = getchar();
6
    for(; c < '0' || c > '9'; c = getchar()) if(c == '-') ne = -1;
7
    for(; c >= '0' && c <= '9'; c = getchar()) s = (s << 1) + (s << 3) + c - '0';
8
    return s * ne;
9
}
10
class PAIR{
11
  public: int x, y;
12
    bool operator < (const PAIR &o) const {return x ^ o.x ? x < o.x : y < o.y;}
13
    bool operator == (const PAIR &o) const {return x == o.x && y == o.y;}
14
} ; set<PAIR> S;
15
PAIR mp(int a, int b) {PAIR o; o.x = a, o.y = b; return o;}
16
int n, q, ans[CN], fa[CN], cnt[CN], to[CN], id[CN], X[CN], Y[CN], tp[CN];
17
bool cmp(int i, int j) {return X[i] ^ X[j] ? X[i] > X[j] : tp[i] > tp[j];}
18
int fd(int x) {return fa[x] ^ x ? fa[x] = fd(fa[x]) : x;}
19
int main(){
20
    freopen("_in.in", "r", stdin);
21
    n = read(); for(int i = 1; i <= n; i++) X[i] = read(), Y[i] = read(), id[i] = i;
22
    q = read(); for(int i = n + 1; i <= n + q; i++) X[i] = read(), Y[i] = read(), tp[i] = i - n, id[i] = i;
23
    sort(id + 1, id + n + q + 1, cmp);
24
    for(int p = 1, i; i = id[p], p <= n + q; p++){
25
        if(tp[i]){
26
            PAIR cur = mp(Y[i], tp[i]); S.insert(cur);
27
            set<PAIR> :: iterator it = S.find(cur); it++;
28
            if(it != S.end()) to[tp[i]] = (*it).y;
29
            it--; while(it != S.begin() && (*--it).y > tp[i]) S.erase(it), it = S.find(cur);
30
        }
31
        else{
32
            PAIR cur = mp(Y[i], 0);
33
            set<PAIR> :: iterator it = S.lower_bound(cur);
34
            if(it != S.end()) cnt[(*it).y]++;
35
        }
36
    }
37
    for(int i = 1; i <= q; i++) fa[i] = i;
38
    for(int i = q; i; i--){
39
        int x = fd(i), y; ans[i] = cnt[x];
40
        if(to[i]) y = fd(to[i]), cnt[y] += cnt[x], fa[x] = y;
41
    }
42
    for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
43
    return 0;
44
}

[HNOI2018] 排列

注意这个限制并不等价于反串的字典序最大！！能转化到字典序模型需要一个“绝对优势”。

考虑一段序列 $A$$A$ 后面接序列 $B$$B$，代价是：

$\sum _{i=1}^{|A|}(pre+i)w_i+\sum _{i=1}^{|B|}(pre+|A|+i)w_i$$\sum\limits_{i=1}^{|A|}(pre+i)w_i+\sum\limits_{i=1}^{|B|}(pre+|A|+i)w_i$

反过来的话，代价是：

$\sum _{i=1}^{|B|}(pre+i)w_i+\sum _{i=1}^{|A|}(pre+|B|+i)w_i$$\sum\limits_{i=1}^{|B|}(pre+i)w_i+\sum\limits_{i=1}^{|A|}(pre+|B|+i)w_i$

$A$$A$ 在 $B$$B$ 前面，就等价于 $-|B|\sum _{i=1}^{|A|}{w}_i+|A|\sum _{i=1}^{|B|}{w}_i>0\iff {\displaystyle \frac{1}{|A|}}\sum _{i=1}^{|A|}{w}_i<{\displaystyle \frac{1}{|B|}}\sum _{i=1}^{|B|}{w}_i$$-|B|\sum\limits_{i=1}^{|A|}w_i+|A|\sum\limits_{i=1}^{|B|}w_i>0\Leftrightarrow \dfrac{1}{|A|}\sum\limits_{i=1}^{|A|}w_i<\dfrac{1}{|B|}\sum\limits_{i=1}^{|B|}w_i$。

对于确定的树形拓扑序，如果可以比较两个段哪个放在前面更好的话，一种通用的贪心方式就是每次找到最优的那个段，把它往父亲合并。

这样就有复杂度 $O(n\log n)$$O(n\log n)$。

扩展 KMP 复习

求 $s$$s$ 和 $s,t$$s,t$ 的每个后缀的 LCP。

定义 $z[i]=\text{LCP}(s,s[i:]]),p[i]=\text{LCP}(s,t[i:])$$z[i]=\text{LCP}(s,s[i:]]),p[i]=\text{LCP}(s,t[i:])$，维护当前匹配出的最靠后的一段 Border $s[l,r]=s[:r-l+1]$$s[l,r]=s[:r-l+1]$，那么如果 $i\le r$$i\le r$，可以发现有：

• $z[i],p[i]\ge min(z[i-l+1],r-i+1)$$z[i],p[i]\ge \min(z[i-l+1],r-i+1)$

直接向后暴力更新就是 $O(n)$$O(n)$。

xxxxxxxxxx
10
1
for(int i = 2, l = 0, r = 0; a[i]; i++){ // 枚举 a 的每个后缀
2
    if(i <= r) z[i] = min(z[i - l + 1], r - i + 1);
3
    while(i + z[i] <= la && a[i + z[i]] == a[z[i] + 1]) z[i]++;
4
    if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
5
}
6
for(int i = 1, l = 0, r = 0; b[i]; i++){ // 枚举 b 的每个后缀
7
    if(i <= r) g[i] = min(z[i - l + 1], r - i + 1);
8
    while(i + g[i] <= lb && b[i + g[i]] == a[g[i] + 1]) g[i]++;
9
    if(i + g[i] - 1 > r) l = i, r = i + g[i] - 1;
10
}

.

2

[CF780F] Axel and Marston in Bitland & [NOI2020] 美食家

考虑构造矩阵 $F_T=|f[T,1]...f[T,n]|$$F_T=|f[T,1]...f[T,n]|$，其中 $f[T,i]$$f[T,i]$ 表示第 $T$$T$ 天在城市 $i$$i$ 的最大价值。

考虑转移矩阵就是邻接矩阵 $W$$W$，其中 $W_{i,j}$$W_{i,j}$ 表示：

• 如果 $i\to j$$i\to j$ 有边，那么 $W_{i,j}=val[j]$$W_{i,j}=val[j]$
• 如果 $i\to j$$i\to j$ 没有边，那么 $W_{i,j}=-\mathrm{\infty }$$W_{i,j}=-\infty$

考虑一次美食节，等价于第 $t_i$$t_i$ 天的转移矩阵发生变化，记为 $W_i$$W_i$，等于把 $W$$W$ 的列向量 $x_i$$x_i$ 整体加 $y_i$$y_i$。

max+ 矩阵乘法满足结合律，但是没有交换律，最终的转移矩阵形式是 $W^{t_1-1}{W}_1{W}^{t_2-t_1-1}{W}_2...$$W^{t_1-1}W_1 W^{t_2-t_1-1}W_2...$。

这样朴素做是 $O(k(5m{)}^3\log T)$$O(k(5m)^3\log T)$，应该能有 35pts。预处理快速幂矩阵应该可以显著减小常数，但是这不本质。

考虑直接 DP 的复杂度是 $O(T{n}^2)$$O(Tn^2)$，那么如果数据分治 $T\le 52501$$T\le 52501$，应该有 40pts+25pts=65pts。

特殊性质 A 非常好做，这样应该就有 75pts。

如果对每个点新建五个点，就是 $O(k(5n{)}^3\log T)$$O(k(5n)^3\log T)$. 75pts.

因为最终结果只需要第一行，如果我们始终维护一个 $1\times n$$1\times n$ 的矩阵做乘法，那么每次乘法实际上是 $O(n^2)$$O(n^2)$ 的，这里复杂度瓶颈在于算快速幂时乘法是 $O(n^3)$$O(n^3)$ 的。

预处理 $2^k$$2^k$ 处的矩阵，那么总复杂度就是 $O((5n{)}^3\log T+(5n{)}^{2}k\log T)$$O((5n)^3\log T+(5n)^2k\log T)$。

[CODE FEST 2016 Grand Final] Water Distribution

对于一个块考虑，它最后整体的和一定是所有点权减掉用过的所有边权，那么最大化这个东西显然需要最小化用过的边权和，那么可以发现这个就是 MST 的边权和。

对每个可能的块预处理，复杂度 $O(2^n\text{poly }n)$$O(2^n\text{poly } n)$。

最后需要若干个块拼起来，这个直接就 $O(3^n)$$O(3^n)$ 枚举子集转移即可。

[51nod 1832] 后序与先序遍历

一棵二叉树如果某个节点只有一个儿子，那么无论这个儿子是它的左儿子或者右儿子，这棵树的先序遍历和后序遍历都是不变的。

先序遍历中 $p[pos[i]+1]$$p[pos[i]+1]$ 一定是 $i$$i$ 的左儿子，后序遍历中 $p^{\prime }[pos[i]-1]$$p'[pos[i]-1]$ 一定是 $i$$i$ 的右儿子。除非不存在，此时 $p[pos[i]+1]=p^{\prime }[pos[i]-1]$$p[pos[i]+1]=p'[pos[i]-1]$。

设只有一个儿子的节点数量为 $cnt$$cnt$，那么答案就是 $2^{cnt}$$2^{cnt}$。

[51nod 1231] 记分牌

竞赛图的一个得分合法，等价于对所有 $k$$k$，前 $k$$k$ 小的得分之和 $\ge (\genfrac{}{}{0ex}{}{k}{2})$$\ge \binom{k}{2}$。

[CF1303F] Number of Components

考虑如果正着做，唯一无法用并查集处理的问题是断掉两个联通块。

如果把这个过程反过来看，又相当于合并两个联通块，因此正反都做一遍即可。

$c_i\le c_{i+1}$$c_i\le c_{i+1}$ 保证了一个联通块至多进行一次断边或连边操作，因此是正确的。

细节？？？

.

3

高斯消元求自由元

[POJ1830] 开关问题

考虑按每个变量列方程，然后高斯消元，判断每个方程的主元是否存在即可求出自由元数量。

在实现上，由于可能无法消元成恰好的对角线矩阵，因此需要倒着枚举变量，回代方程。

$O({\displaystyle \frac{n^3}{\omega }})$$O(\dfrac{n^3}{\omega})$.

[HAOI2018] 反色游戏

考虑有 $m$$m$ 个变量，$n$$n$ 条方程，模 $2$$2$ 意义，求可能的解的数量。设自由元数量是 $cnt$$cnt$，显然答案是 $2^{cnt}$$2^{cnt}$。

XOR方程组的求解

求解 $n$$n$ 条方程，$m$$m$ 个变量的异或方程组。

定义一个指针 $p$$p$ 指向最后一个确定了主元的方程的位置 $+1$$+1$。顺序枚举变量 $i\in [1,m]$$i\in [1,m]$，试图找到一个方程，并把这个方程的主元置为变量 $i$$i$。

如果找不到，那么显然 $i$$i$ 是自由元。否则，设这样的位置是 $q$$q$，那么多了一条确定主元的方程，我们把它放在第 $p$$p$ 个位置上，然后向下消元。

这样我们可以得到一个近似的上三角矩阵，其中第 $p$$p$ 条方程的主元是其第一个满足 $a[p,i]=1$$a[p,i]=1$ 的变量 $i$$i$，并且满足后 $n-p+1$$n-p+1$ 条方程都是无效的方程。

然后考虑回代过程，那么先枚举无效方程，此时方程右边的系数必须为 $0$$0$，否则意味着方程组无解。

然后倒序枚举有主元的方程，我们总能解出该方程的主元的取值，然后向上回代即可。

$O({\displaystyle \frac{m^{2}n}{\omega }})$$O(\dfrac{m^2n}{\omega})$

这样就有 60pts。

xxxxxxxxxx
10
1
int equ(){
2
    int p = 1, ans = 1;
3
    for(int i = 1; i <= m; i++){
4
        if(del[i]) continue; int q = p; while(q <= n && !a[q][i]) q++;
5
        if(q > n) {ans = add(ans, ans); continue;} swap(a[p], a[q]);
6
        for(int j = p + 1; j <= n; j++) if(a[j][i]) a[j] ^= a[p]; p++;
7
    }
8
    for(int i = p; i <= n; i++) if(a[i][m + 1]) return 0;
9
    return ans;
10
}

[HAOI2018] 染色

设 $f[k]$$f[k]$ 表示出现 $S$$S$ 次的颜色恰有 $k$$k$ 种的方案数，$g[k]$$g[k]$ 表示钦点 $k$$k$ 种颜色出现 $S$$S$ 次的方案数。

答案是：$\sum _{i=0}^M{W}_{i}f[i]$$\sum\limits_{i=0}^M W_if[i]$

显然有：$g[k]=\sum _{i=k}^M{\displaystyle (\genfrac{}{}{0ex}{}{i}{k})}f[i]$$g[k]=\sum\limits_{i=k}^M\dbinom{i}{k}f[i]$

那么：$f[k]=\sum _{i=k}^M(-1{)}^{i-k}{\displaystyle (\genfrac{}{}{0ex}{}{i}{k})}g[i]$$f[k]=\sum\limits_{i=k}^M (-1)^{i-k}\dbinom{i}{k}g[i]$

$g[i]={\displaystyle (\genfrac{}{}{0ex}{}{M}{i})}{\displaystyle \frac{N!}{(S!{)}^i(N-iS)!}}(M-i{)}^{N-iS}$$g[i]=\dbinom{M}{i}\dfrac{N!}{(S!)^i(N-iS)!}(M-i)^{N-iS}$

$f[k]=\sum _{i=k}^M(-1{)}^{i-k}{\displaystyle (\genfrac{}{}{0ex}{}{i}{k})}{\displaystyle (\genfrac{}{}{0ex}{}{M}{i})}{\displaystyle \frac{N!}{(S!{)}^i(N-iS)!}}(M-i{)}^{N-iS}$$f[k]=\sum\limits_{i=k}^M(-1)^{i-k}\dbinom{i}{k}\dbinom{M}{i}\dfrac{N!}{(S!)^i(N-iS)!}(M-i)^{N-iS}$

$={\displaystyle \frac{N!M!}{k!}}\sum _{i=0}^{M-k}{\displaystyle \frac{(-1{)}^i}{i!}}\times {\displaystyle \frac{(M-(i+k){)}^{N-(i+k)S}}{(M-(i+k))!(S!{)}^{i+k}(N-(i+k)S)!}}$$=\dfrac{N!M!}{k!}\sum\limits_{i=0}^{M-k}\dfrac{(-1)^i}{i!}\times\dfrac{(M-(i+k))^{N-(i+k)S}}{(M-(i+k))!(S!)^{i+k}(N-(i+k)S)!}$

构造 $a[i]={\displaystyle \frac{(-1{)}^i}{i!}},b[i]={\displaystyle \frac{(M-i{)}^{N-iS}}{(M-i)!(S!{)}^i(N-iS)!}}$$a[i]=\dfrac{(-1)^i}{i!},b[i]=\dfrac{(M-i)^{N-iS}}{(M-i)!(S!)^i(N-iS)!}$，长度均为 $M$$M$。

$f[k]={\displaystyle \frac{N!M!}{k!}}\sum _{i=0}^{M}a[i]b[i+k]$$f[k]=\dfrac{N!M!}{k!}\sum\limits_{i=0}^{M}a[i]b[i+k]$

随便 reverse 即可 $O(n\log n)$$O(n\log n)$.

[Gym - 102978B] Bit Operation

考虑等价于每次选相邻的两个点，然后删掉其中一个。

枚举最后保留下来的点是哪个，那么考虑前后的点必须删掉，显然这个的方案数只和序列长度相关。

考虑枚举最后一次操作删掉了哪个点，如果当前长度为 $i$$i$，那么有 $2(i-1)$$2(i-1)$ 种方案先选择一对点然后再选出一个点，其中一种方案是不可行的，因此有 $f[n]=f[n-1](2n-3)$$f[n]=f[n-1](2n-3)$。

考虑最后前后的操作序列，只需要考虑相对顺序不变来拼接，有组合数系数 ${\displaystyle (\genfrac{}{}{0ex}{}{n-1}{i-1})}$$\dbinom{n-1}{i-1}$。

LGV 引理

在一张 DAG 上，有 $n$$n$ 个起点和 $n$$n$ 个终点。建立一个起点和终点之间的双射 $s\to t$$s\to t$，问有多少路径集合 $\left\{\begin{array}{c}(u_i,v_i)\end{array}\right\}$$\begin{Bmatrix}(u_i,v_i)\end{Bmatrix}$ 满足 $u_i=s_i,v_i=t_i$$u_i=s_i,v_i=t_i$，且路径之间两两不相交。

如果这张 DAG 具备特殊性质，满足有且仅有一种双射能找到合法解，定义邻接矩阵 $G$$G$ 满足 $G_{i,j}$$G_{i,j}$ 表示从 $i$$i$ 起点到 $j$$j$ 终点的路径条数，那么解的数量是 $\text{det }G$$\text{det }G$。

.

4

[NOI2018] 你的名字

考虑如果询问是整串，那么我们只需要用 $S$$S$ 的 SAM 读入 $T$$T$，维护一下当前读入的长度 $T[pos:i]$$T[pos:i]$，那么新增的贡献是 $i-pos+1$$i-pos+1$。

考虑每次跳 $nxt[]$$nxt[]$ 均会删掉 $T$$T$ 当前读入的一段前缀，因此这样的复杂度是 $O(|T|)$$O(|T|)$ 的。

如果询问不是整串，那么只需要知道，某条树边是否存在。只需要维护这条边到达节点的 $endpos$$endpos$，就可以知道 $S[l^{\prime }:r]$$S[l':r]$ 中是否有这个串，也就可以判断这条边是否存在。

[HAOI2018] 字串覆盖

考虑这样一个新的问题：给定串 $S,T$$S,T$，求 $T[l:r]$$T[l:r]$ 在 $S[s:t]$$S[s:t]$ 中第一次出现的位置。

考虑建立广义前缀树，找到 $T[l:r]$$T[l:r]$ 在前缀树上对应的节点，维护 $S$$S$ 的 $endpos$$endpos$ 集合，我们只需要在线段树上二分即可。

xxxxxxxxxx
70
1
#include<bits/stdc++.h>
2
using namespace std;
3
#define lc ch[u][0]
4
#define rc ch[u][1]
5
const int CN = 1e5 + 10;
6
int read(){
7
    int s = 0, ne = 1; char c = getchar();
8
    for(; c < '0' || c > '9'; c = getchar()) if(c == '-') ne = -1;
9
    for(; c >= '0' && c <= '9'; c = getchar()) s = (s << 1) + (s << 3) + c - '0';
10
    return s * ne;
11
}
12
int n, q, pos[CN], pb[CN], len[CN << 2], nxt[CN << 2], fa[20][CN << 2], son[CN << 2][26], idx; char S[CN], T[CN];
13
void ins(char ch[], bool tp){
14
    for(int i = 1, u = 0, c; c = ch[i] - 'a', ch[i]; i++){
15
        if(!son[u][c]) son[u][c] = ++idx; u = son[u][c];
16
        if(tp) pos[i] = u; else pb[i] = u;
17
    }
18
}
19
int et(int p, int c){
20
    int u = son[p][c]; if(len[u]) return u; len[u] = len[p] + 1, p = nxt[p];
21
    while(p ^ -1 && !son[p][c]) son[p][c] = u, p = nxt[p];
22
    if(p == -1) return u; int d = son[p][c];
23
    if(len[d] == len[p] + 1) return nxt[u] = d, u;
24
    int v = ++idx; len[v] = len[p] + 1, nxt[v] = nxt[d], nxt[d] = nxt[u] = v;
25
    for(int i = 0; i < 26; i++) if(len[son[d][i]]) son[v][i] = son[d][i];
26
    while(p ^ -1 && son[p][c] == d) son[p][c] = v, p = nxt[p];
27
    return u;
28
}
29
class PAIR {public: int x, y;}; queue<PAIR> Q;
30
PAIR mp(int a, int b) {PAIR o; o.x = a, o.y = b; return o;}
31
void bd(){
32
    for(int i = 0; i < 26; i++) if(son[0][i]) Q.push(mp(0, i));
33
    while(!Q.empty()){
34
        int u = Q.front().x, c = Q.front().y; Q.pop(), u = et(u, c);
35
        for(int i = 0; i < 26; i++) if(son[u][i]) Q.push(mp(u, i));
36
    }
37
}
38
int rt[CN << 2], ch[CN * 70][2], cnt[CN], id[CN << 2], sidx; bool d[CN * 70];
39
void md(int &u, int l, int r, int p){
40
    if(!u) u = ++sidx; if(l == r) return (void)(d[u] |= 1);
41
    int m = (l + r) >> 1; p <= m ? md(lc, l, m, p) : md(rc, m + 1, r, p);
42
    d[u] = d[lc] | d[rc];
43
}
44
int mg(int x, int y, int l, int r){
45
    if(!(x * y)) return x + y; int u = ++sidx, m = (l + r) >> 1;
46
    d[u] = d[x] | d[y]; if(l == r) return u;
47
    lc = mg(ch[x][0], ch[y][0], l, m), rc = mg(ch[x][1], ch[y][1], m + 1, r);
48
    d[u] = d[lc] | d[rc]; return u;
49
}
50
int qu(int u, int l, int r, int s, int t){
51
    if(!d[u]) return 0; if(l == r) return l; int m = (l + r) >> 1, tmp;
52
    if(s <= m) {tmp = qu(lc, l, m, s, t); if(tmp) return tmp;}
53
    return m < t ? qu(rc, m + 1, r, s, t) : 0;
54
}
55
int main(){
56
    nxt[0] = -1, scanf("%s%s", S + 1, T + 1), n = strlen(S + 1), ins(S, 1), ins(T, 0), bd();
57
    for(int i = 1; i <= n; i++) md(rt[pos[i]], 1, n, i);
58
    for(int i = 1; i <= idx; i++) cnt[len[i]]++; for(int i = n; i; i--) cnt[i] += cnt[i + 1];
59
    for(int i = 1; i <= idx; i++) id[cnt[len[i]]--] = i;
60
    for(int p = 1, i; i = id[p], p <= idx; p++) if(nxt[i]) rt[nxt[i]] = mg(rt[nxt[i]], rt[i], 1, n);
61
    memcpy(fa[0], nxt, sizeof(nxt)), fa[0][0] = 0;
62
    for(int k = 1; k < 20; k++) for(int i = 1; i <= idx; i++) fa[k][i] = fa[k - 1][fa[k - 1][i]];
63
    q = read(); while(q--){
64
        int l = read(), r = read(), s = read(), t = read(), u = pb[t];
65
        for(int k = 19; k + 1; k--) if(len[fa[k][u]] >= t - s + 1) u = fa[k][u];
66
        if(t - s > r - l) puts("0");
67
        else printf("%d\n", max(0, qu(rt[u], 1, n, l + t - s, r) - t + s));
68
    }
69
    return 0;
70
}

那么只需要每次暴力寻找下一个即是 $O({\displaystyle \frac{n\log n}{|T^{\prime }|}})$$O(\dfrac{n\log n}{|T'|})$，考虑数据分治一下瞎搞就做完了，垃圾题。

[HAOI2018] 奇怪的背包

需要注意到一个非常重要的事情：所有有效数字都应当是 $P$$P$ 的因子，而 $P$$P$ 的因子并不是很多。

首先把 $a[i]$$a[i]$ 变成 $(a[i],P)$$(a[i],P)$，那么答案不改变，去重以后，选一个因子有 $2^s-1$$2^s-1$ 种方法。

直接对着 $P$$P$ 的因子 DP，最后暴力枚举两个因子合并答案，复杂度 $O({\sigma }_0(P{)}^2\log P)-O(1)$$O(\sigma_0(P)^2\log P)-O(1)$。

[HAOI2018] 苹果树

给点第 $i$$i$ 次操作的点标号 $i$$i$，然后考虑枚举一个点，算这个点上面那条边的贡献，就是 $sz[i](n-sz[i])$$sz[i](n-sz[i])$。

考虑枚举 $sz[i]$$sz[i]$，然后算方案数。前面构造到 $i$$i$ 有 $i!$$i!$ 种方案，后面还剩 $n-i$$n-i$ 次操作。先选出 $i$$i$ 的子树，显然是 ${\displaystyle (\genfrac{}{}{0ex}{}{n-i}{sz[i]-1})}sz[i]!$$\dbinom{n-i}{sz[i]-1}sz[i]!$，然后后面的点不能选在 $i$$i$ 的子树里，应当是 $(i-1{)}^{\overline{n-i-sz[i]+1}}$$(i-1)^{\overline {n-i-sz[i]+1}}$，这部分乘起来就是：

$i!(i-1{)}^{\overline{n-i-sz[i]+1}}{\displaystyle (\genfrac{}{}{0ex}{}{n-i}{sz[i]})}sz[i]!=sz[i]!{\displaystyle (\genfrac{}{}{0ex}{}{n-i}{sz[i]-1})}(n-sz[i]-1)!i(i-1)$$i!(i-1)^{\overline{n-i-sz[i]+1}}\dbinom{n-i}{sz[i]}sz[i]!=sz[i]!\dbinom{n-i}{sz[i]-1}(n-sz[i]-1)!i(i-1)$

答案是：

$\sum _{i=2}^{n}i(i-1)\sum _{s=1}^{n-1}{\displaystyle (\genfrac{}{}{0ex}{}{n-i}{s-1})}s·s!(n-s)!$$\sum\limits_{i=2}^ni(i-1)\sum\limits_{s=1}^{n-1}\dbinom{n-i}{s-1}s·s!(n-s)!$

应该可以卷积。

[JSOI2019] 节日庆典

我们知道对于最小表示法问题，有一个 $O(n)$$O(n)$ 的 lyndon 分解解法：

• 对串 $AA$$AA$ lyndon 分解，找到第 $|A|$$|A|$ 个位置所在的 lyndon 串，那么最小表示法即是该字符串以这个 lyndon 串为起始的轮换

这样做就是 $O(n^2)$$O(n^2)$ 的，可以拿到 30pts 的好成绩。

先考虑一个错误的贪心：取字典序最小的后缀。这个贪心的错因在于接上前缀之后，字典序可能会变大，但是这启发我们，有用的后缀是字典序最小的那些后缀。

形式化地，我们定义一个后缀 $s[i:]$$s[i:]$ 有用，当且仅当仅不存在一个后缀严格小于它。这里 $s$$s$ 严格小于 $t$$t$ 指可以找到一个位置 $p\in [1,min|s|,|t|]$$p\in [1,\min |s|,|t|]$，使得 $s_p<t_p$$s_p<t_p$ 且 $s[1:p-1]=t[1:p-1]$$s[1:p-1]=t[1:p-1]$。

可以发现，如果相邻的两个有用的后缀中，后面那个到前面那个的距离小于后面的串长，那么后面的那个没有用处。这说明了有用的后缀数量是 $O(\log n)$$O(\log n)$ 的。

考虑维护有用的后缀构成的集合 $S$$S$，记对于前缀 $i$$i$，维护出的集合是 $S_i$$S_i$，那么有 $S_{i+1}\subseteq S_i\cup \left\{\begin{array}{c}i+1\end{array}\right\}$$S_{i+1}\subseteq S_i\cup \begin{Bmatrix} i+1\end{Bmatrix}$。

考虑由 $S_{i-1}$$S_{i-1}$ 构造 $S_i$$S_i$，我们枚举 $x\in S_{i-1}$$x\in S_{i-1}$，那么只需要考虑它和 $S_i$$S_i$ 中最后一个元素 $y$$y$，新增出来的这一位之间的大小关系，即比较两个字符的大小。这样可以确定保留 $x$$x$ 或者 $y$$y$。

然后再集合中新增 $i$$i$ 即可。

考虑如何计算前缀 $i$$i$ 时的答案，那么从前向后枚举每一个选出来的后缀，维护前面选出的最优解是 $x$$x$，当前枚举到的解是 $y$$y$，那么显然有 $|s[x:i]|>|s[y:i]|$$|s[x:i]|>|s[y:i]|$，并且 $s[y:i]$$s[y:i]$ 是 $s[x:i]$$s[x:i]$ 的前缀。那么我们只需要比较剩下的部分，也就是比较 $s[x+i-y+1:]$$s[x+i-y+1:]$ 和 $s[1:n]$$s[1:n]$ 的大小关系即可，这个可以扩展 KMP 预处理。

因此复杂度 $O(n\log n)$$O(n\log n)$。

.

5

[CF547E] Mike and Friends

考虑类比两个串的做法，先建立广义前缀树，那么一次询问相当于是问某个子树内，线段树上一个区间里面所有出现次数的和。

乍一看这是个二维的东西，考虑有一维是没用的，能不能减少一维。

这样定义线段树：$u$$u$ 节点的线段树区间 $[i,i]$$[i,i]$ 表示 $u$$u$ 节点的所有子串在 $i$$i$ 这个串里的出现次数。

那么依然可以线段树合并来更新，然后就没了，但是空间怎么算都不够用。

有一个利用 fail 树性质的做法：

先对所有串建立 AC 自动机，维护出每个串的接受状态。考虑将答案差分，变成询问在一个前缀内，某个串在其它串中的出现次数，那么只需要用 AC 自动机顺序读入每个串，将节点上的贡献 $+1$$+1$。那么 $r=i$$r=i$ 的询问的答案，就是 $s_k$$s_k$ 接受状态的那个子树权值的和，直接 BIT 维护即可。

时间复杂度 $O(n\log n)$$O(n\log n)$，空间复杂度 $O(n|\mathrm{\Sigma }|)$$O(n|\Sigma|)$。

考虑这个题的启发是：

• 一个子串在这个串里面出现了多少次：SAM
• 一个前缀在这个串里面出现了多少次：KMP (Border)

那么：

• 一个串的子串在另一个串的子串里面出现了多少次：多串 SAM + 子树查询
• 一个串在另一个串中出现了多少次：多串 KMP + 子树查询

[SRM550, R1 div1] Conversion Machine

考虑先把 $S$$S$ 最小步数变成 $T$$T$，那么对于第 $i$$i$ 位，走过的步数一定是 $a_i+3b_i$$a_i+3b_i$ 的形式。

考虑剩下部分走的总步数，设为 $t$$t$，那么关系是 $\sum step[i]+t\mathrm{\Sigma }\le lim$$\sum step[i]+t\Sigma\le lim$，从而可以解出 $t$$t$ 的上界 $X$$X$。

设剩下部分还要走 $i$$i$ 步的答案是 $f_i$$f_i$，那么答案就是 $\sum _{i=0}^X{f}_i$$\sum\limits_{i=0}^X f_i$，其中有 $f_n=n![x^n]\prod _i{F}_i(x)$$f_n=n![x^n]\prod\limits_i F_i(x)$。

考虑一个抽象的问题模型：

用 $m$$m$ 种颜色涂长为 $n$$n$ 的序列，记有 $k_i$$k_i$ 个格子涂上了第 $i$$i$ 种颜色，则需要满足 $\mathrm{\forall }i\in [1,m],k_i\equiv a_i(\mathrm{mod}3)$$\forall i\in[1,m], k_i\equiv a_i\pmod 3$，问有多少种不同的序列。两个序列不同，当且仅当某个位置涂上的颜色不同。

$m\le 11,n\le {10}^9,0\le a_i<3$$m\le 11, n\le 10^9, 0\le a_i<3$

考虑对每种颜色构造 EGF，即 $G_n(x)=\sum _i[imod3=a_n]{\displaystyle \frac{x^i}{i!}}$$G_n(x)=\sum\limits_{i}[i\bmod 3=a_n]\dfrac{x^i}{i!}$，那么答案是 $n![x^n]\prod _i{G}_i(x)$$n![x^n]\prod\limits_i G_i(x)$。

考虑单位根反演，那么 $G_n(x)=\sum _i{\displaystyle \frac{1}{3}}\sum _{k=0}^2{\omega }_3^{k(i-a_n)}{\displaystyle \frac{x^i}{i!}}={\displaystyle \frac{1}{3}}\sum _{k=0}^2{\omega }_3^{-k{a}_n}{e}^{{\omega }_3^{k}x}$$G_n(x)=\sum\limits_i\dfrac{1}{3} \sum\limits_{k=0}^2\omega_3^{k(i-a_n)}\dfrac{x^i}{i!}=\dfrac{1}{3}\sum\limits_{k=0}^2 \omega_3^{-ka_n}e^{\omega_3^kx}$。

那么答案就是 $[x^n]{\displaystyle \frac{n!}{3^n}}\prod _i(e^x+{\omega }_3^{-a_i}{e}^{{\omega }_{3}x}+{\omega }_3^{-2a_i}{e}^{{\omega }_3^{2}x})$$[x^n]\dfrac{n!}{3^n}\prod\limits_i(e^x+\omega_3^{-a_i}e^{\omega_3 x}+\omega_3^{-2a_i}e^{\omega_3^2x})$。

可以 $3^n$$3^n$ 暴力展开 product，那么答案累加 ${\displaystyle \frac{A{B}^n}{3^n}}$$\dfrac{AB^n}{3^n}$，其中 $A$$A$ 是多项式前面的系数乘积，$B$$B$ 是指数上 $x$$x$ 的系数和。

注意到 ${\omega }_3=e^{\text{i}\frac{2\pi }{3}}={\displaystyle \frac{\sqrt{3}\text{i}-1}{2}}$$\omega_3=e^{\text i\frac{2\pi}{3}}=\dfrac{\sqrt 3\,\text i-1}{2}$，令 ${\text{i}}^2=-3$$\text i^2=-3$ 扩域计算即可。

.

6

[NOIAC D1 A] 异或

• 对于 $a,b,c\in \mathbb{N}$$a,b,c\in \mathbb N$，如果 $a\le b\le c$$a\le b\le c$，那么 $a\oplus c\ge mina\oplus b,b\oplus c$$a\oplus c\ge \min a\oplus b, b\oplus c$。

证明：

首先有取等的条件是 trivial 的，对于 $a<b<c$$a<b<c$ 的情况，首先对高位考虑。

如果 $a,b,c$$a,b,c$ 的最高位均相同，可以规约到去掉最高位时的情况；

如果 $a,b,c$$a,b,c$ 的最高位均不相同，那么结论直接成立；

如果 $a,b$$a,b$ 的最高位相同且与 $c$$c$ 不同，那么结论直接成立；

如果 $b,c$$b,c$ 的最高位相同且与 $a$$a$ 不同，那么结论直接成立。

那么判断一个集合合法，只需要将其排序即可。

设 $p$$p$ 是满足 $2^i\ge x$$2^i\ge x$ 的最小的 $i$$i$，将 $a[]$$a[]$ 去除低 $p$$p$ 位后分类，那么不同组之间显然是随便选，同一组内选择的数，必须满足第 $p$$p$ 位互不相同。

那么一个组里面只能不选，选一个或者选两个，算出每组的方案数相乘即可。

选两个的时候，相当于求有多少数，和一个数异或 $\ge x$$\ge x$，直接 Tire 维护即可。

特殊情况是 $x=0$$x=0$，特判即可。

xxxxxxxxxx
13
1
#define lc ch[u][0]
2
#define rc ch[u][1]
3
int rt, ch[CN * 60][2], sz[CN * 60], idx;
4
void ins() {}
5
int qu(int u, int dep, LL x, LL y){ // ai ^ x <= y
6
    if(dep < 0) return sz[u];
7
    if((y >> dep) & 1){
8
        if((x >> dep) & 1) return qu(lc, dep - 1, x, y);
9
        return qu(rc, dep - 1, x, y);
10
    }
11
    if((x >> dep) & 1) return sz[lc] + qu(rc, dep - 1, x, y);
12
    return sz[rc] + qu(lc, dep - 1, x, y);
13
}

.

7

[NOIAC D2 A] 矩阵填数

一个 $n\times m$$n\times m$ 的网格，每个位置需要填 $[1,m]$$[1,m]$ 的数字。给定 $q$$q$ 条限制 $[(x_1,y_1),(x_2,y_2),v]$$[(x_1,y_1),(x_2,y_2), v]$ 表示从 $(x_1,y_1)$$(x_1,y_1)$ 到 $(x_2,y_2)$$(x_2,y_2)$ 的最大值必须是 $v$$v$，求有多少种方案。

考虑如果限制矩形均不相交，那么答案很容易计算。

考虑如果两个 $v$$v$ 不相等的矩形相交了，那么显然 $v$$v$ 小的那个会控制相交的区域。但是如果 $v$$v$ 相等呢？这就比较难处理。

先只考虑 $v$$v$ 互不相同的情况，那么显然将矩形排序，然后枚举一个矩形，就只需要算出在它前面的的矩形，与它的交覆盖的总面积，这部分是由这个矩形控制的。

如果只有一种 $v$$v$ 呢。考虑枚举一个集合 $S$$S$，然后算 $S$$S$ 个矩形均不满足限制的方案数容斥，这个很容易计算。

考虑把这两种做法合并起来，那么考虑先算出这种 $v$$v$，去除之前的矩形的并，覆盖的总面积，这就是全集，然后枚举一个集合容斥计算全集的合法方案数即可，最后答案就是所有 $v$$v$ 乘起来。

考虑难求出的东西是一个集合覆盖的总面积 $cu[S]$$cu[S]$，显然 $cu[S]=\sum _{T\subseteq S}(-1{)}^{|T|-1}ca[T]$$cu[S]=\sum\limits_{T\subseteq S} (-1)^{|T|-1}ca[T]$，那么直接高维前缀和计算即可。

复杂度 $O(n{2}^n)$$O(n2^n)$。

Manacher 复习

Manacher 和扩展 KMP 算法有着异曲同工之妙，都是维护一些特殊结构，然后达到均摊 $O(n)$$O(n)$ 的复杂度。

Manacher 用于求出字符串某个位置的回文半径，定义为 $\lceil {\displaystyle \frac{l}{2}}\rceil$$\lceil\dfrac{l}{2} \rceil$，其中 $l$$l$ 表示以该位置为回文中心的串的最长长度。

对于偶数串 $s$$s$ 的回文中心，我们认为它在 $\lfloor {\displaystyle \frac{|s|}{2}}\rfloor$$\lfloor\dfrac{|s|}{2} \rfloor$ 这个位置。

Manacher 维护一个当前找到的右边界最靠右的回文子串 $[l_0,r_0]$$[l_0,r_0]$，那么可以发现 $r[i]\ge minp+r[p]-i,r[2p-i]$$r[i]\ge \min p+r[p]-i,r[2p-i]$，其中 $[p-r[p],p+r[p]]$$[p-r[p], p+r[p]]$ 是当前维护的回文子串。可以证明这样做的复杂度是 $O(n)$$O(n)$。

扩展 KMP 用于求出一个串 $s$$s$ 和它的每一个后缀 $s[i:]$$s[i:]$ 的 LCP $z[i]$$z[i]$。

维护当前找到的右端点最靠右的一段 Border $[l,r]$$[l,r]$，那么如果 $i\le r$$i\le r$，可以发现 $z[i]\ge minz[i-l+1],r-i+1$$z[i]\ge \min z[i-l+1],r-i+1$。可以证明这样做的复杂度是 $O(n)$$O(n)$。

最长回文前后缀这种东西还是回文树吧...

.

8

[CF573E] Bear and Bowling

$O(n!)$$O(n!)$ 爆搜的常见优化是 $O(2^n)$$O(2^n)$ 状压，$O(2^n)$$O(2^n)$ 爆搜的常见优化是 $O(n^2)/O(\text{poly }n)$$O(n^2)/O(\text{poly }n)$ DP，这个要记清楚了。

那么考虑一个 naive 的 DP：设 $f[i,j]$$f[i,j]$ 表示考虑前 $i$$i$ 位，选了 $j$$j$ 个，可以发现这个状态是容易转移的。

设 $f[j]$$f[j]$ 表示选 $j$$j$ 个数的最优答案，考虑加入一个 $i$$i$，更新到的一定是一段后缀。直接数据结构维护就好了。

[HDU3306] Another Kind of Fibonacci

考虑 $f_n^2=(A{f}_{n-1}+B{f}_{n-2}{)}^2=A^2{f}_{n-1}^2+B^2{f}_{n-2}^2+2AB{f}_{n-1}{f}_{n-2}$$f^2_n=(Af_{n-1}+Bf_{n-2})^2=A^2f^2_{n-1}+B^2f^2_{n-2}+2AB f_{n-1}f_{n-2}$；

$f_n{f}_{n-1}=(A{f}_{n-1}+B{f}_{n-2})f_{n-1}=A{f}_{n-1}^2+B{f}_{n-2}{f}_{n-1}$$f_{n}f_{n-1}=(Af_{n-1}+Bf_{n-2})f_{n-1}=Af_{n-1}^2+Bf_{n-2}f_{n-1}$。

这样就可以维护了。也就是说维护乘积求和的时候要试图找乘积的递推关系。

维护 $\begin{array}{cccc}|s_n& f_n^2& f_{n-1}^2& f_n{f}_{n-1}|\end{array}$$\begin{matrix}|s_n &f^2_n&f^2_{n-1}&f_nf_{n-1}|\end{matrix}$，转移矩阵是 $\left|\begin{array}{cccc}1& 0& 0& 0\\ A^2& A^2& 1& A\\ B^2& B^2& 0& 0\\ 2AB& 2AB& 0& B\end{array}\right|$$\begin{vmatrix}1&0&0&0\\A^2&A^2&1&A\\B^2&B^2&0&0\\2AB&2AB&0&B\end{vmatrix}$。

特征方程复习

• 一阶：构造等比递推

对于一阶递推 $x_n=p{x}_{n-1}+q$$x_n=px_{n-1}+q$，尝试构造等差数列：

设 $d$$d$ 满足 $x_n-d=p(x_{n-1}-d)$$x_n-d=p(x_{n-1}-d)$，推得 $x_n=p{x}_{n-1}+(1-p)d$$x_n=px_{n-1}+(1-p)d$，也就是 $(1-p)d=q,d={\displaystyle \frac{q}{1-p}}$$(1-p)d=q,d=\dfrac{q}{1-p}$。

那么 $\left\{\begin{array}{c}x\end{array}\right\}-d$$\begin{Bmatrix}x\end{Bmatrix}-d$ 是等比数列，$x_n^{\prime }=p^n{x}_0^{\prime }$$x'_n=p^nx'_0$，其中 $x_0^{\prime }=x_0-d,x_n^{\prime }=x_n-d$$x'_0=x_0-d,x'_n=x_n-d$。

• 高阶

对于 $x_n=a{x}_{n-1}+b{x}_{n-2}$$x_n=ax_{n-1}+bx_{n-2}$，用 $x^n$$x^n$ 代 $x_n$$x_{n}$，得到方程 $x^n=a{x}^{n-1}+b{x}^{n-2}$$x^n=ax^{n-1}+bx^{n-2}$，化简得到 $x^2-ax-b=0$$x^2-ax-b=0$。

设它的两个特征根是 $X_0,X_1$$X_0,X_1$，那么存在系数 $A,B$$A,B$，使得：

$x_n=A{X}_0^n+B{X}_1^n$$x_n=AX_0^n+BX_1^n$

使用前两项解出系数即可。

[HDU2256] Problem of Precision

首先求 $(\sqrt{2}+\sqrt{3}{)}^{2n}mod1024$$(\sqrt 2+\sqrt 3)^{2n}\bmod 1024$ 就直接做，但是现在要求 $\lfloor (\sqrt{2}+\sqrt{3}{)}^{2n}\rfloor mod1024$$\lfloor(\sqrt 2+\sqrt 3)^{2n}\rfloor\bmod 1024$。

$(\sqrt{2}+\sqrt{3}{)}^{2n}=(5+2\sqrt{6}{)}^n$$(\sqrt 2+\sqrt 3)^{2n}=(5+2\sqrt 6)^n$

我们知道 $(5+2\sqrt{6}{)}^n+(5-2\sqrt{6}{)}^n=2\text{Re}[(5+2\sqrt{6}{)}^n]$$(5+2\sqrt 6)^n+(5-2\sqrt 6)^n = 2\text{Re}[(5+2\sqrt 6)^n]$。

而 $(5-2\sqrt{6})=0.101...$$(5-2\sqrt 6)=0.101...$ 是个小于 $1$$1$ 的数字。

那么 $\lfloor (5+2\sqrt{6}{)}^n\rfloor =\lfloor 2\text{Re}[(5+2\sqrt{6}{)}^n]-eps\rfloor$$\lfloor(5+2\sqrt 6)^n\rfloor=\lfloor2\text{Re}[(5+2\sqrt 6)^n]-eps\rfloor$，其中 $0<eps<1$$0<eps<1$。

那么答案就是 $2\text{Re}[(5+2\sqrt{6}{)}^n]-1$$2\text{Re}[(5+2\sqrt 6)^n]-1$，扩域即可。

树状数组上倍增

树状数组的 $d[i]$$d[i]$ 维护的是 $[i-\text{lowbit}(i)+1,i]$$[i-\text{lowbit}(i)+1,i]$ 这一段区间的和，如果我要问 $[i+1,i+2^k]$$[i+1, i+2^k]$ 这段区间的和，就对应到 $d[i+2^k]$$d[i+2^k]$，前提是 $k$$k$ 是 $i$$i$ 的 lowbit，我们发现倍增过程恰好满足这个性质。

[联合省选2020 A] 冰火战士

考虑先把两个数组都升序排序，以下做法基于该结论讨论：

找到最后一个满足 $si(i)\le sf(i)$$si(i)\le sf(i)$ 的温度 $i$$i$，和第一个满足 $si(j)>sf(j)$$si(j)>sf(j)$ 的温度 $j$$j$，答案出自 $i,j$$i,j$ 中的一个。

考虑如果倍增一个温度 $T$$T$，需要对 $ai$$ai$ 求前缀和，对 $af$$af$ 求后缀和，这不太好办。那么做差值，把 $af$$af$ 取反，温度 $-1$$-1$，用当前的总和减掉前缀和即可。

BIT 上倍增即可 $O(n\log n)$$O(n\log n)$。

灵光一现

求两个字符串 $S,T$$S,T$ 内共出现了多少个本质不同的子串。

• 解一：对这两个字符串建广义 SAM（Trie 树上建 SAM），统计每个节点的贡献即可。
• 解二：等价于 $S$$S$ 的本质不同子串数 + $T$$T$ 的本质不同子串数 - $S,T$$S,T$ 共同的本质不同子串数。$S,T$$S,T$ 共同的本质不同子串，可以在建立 $T$$T$ 的 SAM 的同时，在 $S$$S$ 的 SAM 中读入 $T$$T$，然后考虑 $T[i]$$T[i]$ 的贡献，就是 $max(0,ml-le{n}_T[nx{t}_T[u]])$$\max(0, ml-len_T[nxt_T[u]])$，其中 $ml$$ml$ 是当前匹配长度。

基环树的 Prufer 序列构造

每次找到编号最小的一个叶子，把它的父亲加入序列。如果它的父亲在环上，那么不删除；否则删除这个父亲。

那么可以发现，树上点 $u$$u$ 在序列中出现次数是 $d_u-1$$d_u-1$，环上点 $u$$u$ 在序列中出现次数是 $d_u-2$$d_u-2$，并且序列中最后一个点一定是环上的点，并且序列的长度 = 点数 - 环长。

如果这个时候已经确定了环的形态，那么就可以确定这个基环树。这里的形态指的是有哪些点，以及点的顺序。

注意一个大环没办法用这种构造表出，或者说表出的结果是空序列 + 大环。

[Code FEST 2017 R3 J] Unicyclic Graph Counting

给定 $n$$n$ 个点各自的度数 $d_1...d_n$$d_1...d_n$，求有多少个满足该度数序列的有标号基环树。

直接 DP 对推广的 Prufer 序列计数，维护 $\sum \prod {\displaystyle \frac{1}{(d_i-k)!}},k=1/2$$\sum\prod \dfrac{1}{(d_i-k)!},k=1/2$，即可 $O(n^2)$$O(n^2)$。

注意 $n$$n$ 个点的有标号环有 ${\displaystyle \frac{(n-1)!}{2}}$$\dfrac{(n-1)!}{2}$ 种形态。

毒瘤

$n$$n$ 个点的有标号树有 $n^{n-1}$$n^{n-1}$ 种形态，那么 $n$$n$ 个点的有标号基环树有多少种形态？

树是简单图，因此不能有自环或者重边。

先枚举一个环长，构造上面的序列，有：${\displaystyle \frac{(n-1)!}{2}}+{\displaystyle \frac{1}{2}}\sum _{l=3}^{n-1}{n}^{\underset{―}{l}}{n}^{n-l-1}$$\dfrac{(n-1)!}{2}+\dfrac{1}{2}\sum\limits_{l=3}^{n-1}n^{\underline l}n^{n-l-1}$

OEIS-A057500

.

9

同余最短路

你一开始在 $0$$0$ 处，每次可以走 $a_i,i\in [1,n]$$a_i,i\in[1,n]$ 步，求你在 $[0,m]$$[0,m]$ 中能到达多少不同的点。$m$$m$ 很大，但是 $min{a}_i$$\min a_i$ 很小。

设 $b=min{a}_i$$b=\min a_i$，那么每个 $a_i$$a_i$ 都可以被表示成 $k_{i}b+r_i$$k_ib+r_i$ 的形式，其中 $k_i\ge 1,0\le r_i<b$$k_i\ge 1, 0\le r_i<b$。

设 $d[i]=x$$d[i]=x$ 表示满足 $xmodb=i$$x\bmod b=i$ 的，最小能到达的点 $x$$x$。那么形如 $d[i]+pb$$d[i]+pb$ 的点都可以到达，如果能对每个 $i\in [0,b)$$i\in[0,b)$ 求出 $d[i]$$d[i]$，我们就能解出问题的答案。

考虑对每个 $a_i$$a_i$ 和 $j\in [0,b)$$j\in[0, b)$，连边 $(j,(j+a_i)modb,a_i)$$(j,(j+a_i)\bmod b,a_i)$，那么 $d[i]$$d[i]$ 等价于在这张点数 $O(b)$$O(b)$，边数 $O(bn)$$O(bn)$ 的图上从 $0$$0$ 到 $i$$i$ 的最短路，使用 Dijkstra 求解即可。

[WC2016] 论战捆竹竿

显然等价于一个模型：一开始在 $0$$0$，每次可以走 $a_i$$a_i$ 步，问 $[0,w-n]$$[0, w-n]$ 中可以到达多少点。这里 $a_i=n-|\text{Border}[i]|$$a_i=n-|\text{Border}[i]|$。

显然 $min{a}_i$$\min a_i$ 是 $O(n)$$O(n)$ 级别的，那么直接建图是 $O(n^2)$$O(n^2)$ 的，这样有 50pts。

• 一个串 $s$$s$ 的所有 Border 排序后，会形成 $O(\log |s|)$$O(\log |s|)$ 段等差数列。

不会了/kk

reflect

线段树合并的时候，判断要这样写：

xxxxxxxxxx
1
1
if(!u || !v) return u | v;

不要用乘积！！乘积会溢出，很可能被对着卡！！

• 对拍必须写，先打好暴力。第一遍先打暴力，第二遍再想题，注意时间。

[THUSCH2017] 大魔法师

先把信息写成向量的形式，然后通过矩阵来进行变换。

$\left|\begin{array}{ccc}{A}_i& B_i& C_i\end{array}\right|$$\begin{vmatrix}A_i &B_i&C_i \end{vmatrix}$

考虑 1 操作，相当于乘上 $\left|\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 0& 0& 1\end{array}\right|$$\begin{vmatrix}1&0&0\\1&1&0\\0&0&1 \end{vmatrix}$；

考虑 2 操作，相当于乘上 $\left|\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 1& 1\end{array}\right|$$\begin{vmatrix}1&0&0\\0&1&0\\0&1&1 \end{vmatrix}$；

考虑 3 操作，相当于乘上 $\left|\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 0& 0& 1\end{array}\right|$$\begin{vmatrix}1&0&1\\0&1&0\\0&0&1 \end{vmatrix}$；

考虑 4 操作，相当于加上 $\left|\begin{array}{ccc}v& 0& 0\end{array}\right|$$\begin{vmatrix}v&0&0 \end{vmatrix}$；

考虑 5 操作，相当于乘上 $\left|\begin{array}{ccc}1& 0& 0\\ 0& v& 0\\ 0& 0& 1\end{array}\right|$$\begin{vmatrix}1&0&0\\0&v&0\\0&0&1 \end{vmatrix}$；